package cn.edu.besti.cs1723.TX2305;

//import eighthweek.LinkedBinarySearchTree;

import eighthweek.LinkedBinarySearchTree;

import static Chap10.Searching.linearSearch;

public class Searching {
    //顺序查找
    public static <T extends Comparable<T>> boolean LinearSearch(T[] data, int min, int max, T target) {
        int index = min;
        boolean found = false;
        while (!found && index <= max) {
            found = data[index].equals(target);
            index++;
        }
        return found;
    }
    //二叉查找
    public static <T extends Comparable<? super T>> boolean BinarySearch(T[] data, int min, int max, T target) {
        boolean flag= false;
        int mid = (max+min)/2;
        if(data[mid].compareTo(target)==0){
            flag = true;
        }else if(data[mid].compareTo(target)>0){
            if(min<=mid-1){
                flag = BinarySearch(data, min, mid-1, target);
            }
        }else if(data[mid].compareTo(target)<0){
            if(mid+1<=max){
                flag = BinarySearch(data, mid+1, max, target);
            }
        }
        return flag;
    }
    //折半查找
    public static int InsertionSearch(int data[], int target) {
        int low = 0, mid, high = data.length - 1;
        while (low < high){
            mid = low + ( high - low ) * ( target - data[low] ) / ( data[high] - data[low] );
            if(target > data[mid])
                low = mid + 1;
            else if (target < data[mid])
                high = mid - 1;
            else
                return mid + 1;
        }
        return -1;
    }
    //斐波那契查找
    public static Comparable FibonacciSearch(Comparable[] data, Comparable target) {
        int low = 0, high = data.length - 1, mid, temp1 = 0, temp2;
        int[] fibonacci = fibonacci(data.length);
        while (data.length > fibonacci[temp1] - 1) {
            temp1++;
        }
        int[] temp = new int[fibonacci[temp1] - 1];
        for (int j = 0; j < data.length; j++) {
            temp[j] = (int)data[j];
        }
        for (temp2 = data.length; temp2 < fibonacci[temp1] - 1; temp2++) {
            temp[temp2] = temp[high];
        }
        while (low <= high) {
            mid = low + fibonacci[temp1 - 1] - 1;
            if (temp[mid] > (int)target) {
                high = mid - 1;
                temp1 = temp1 - 1;
            } else if (temp[mid] < (int)target) {
                low = mid + 1;
                temp1 = temp1 - 2;
            } else {
                if (mid <= high) {
                    return mid + 1;
                } else {
                    return high + 1;
                    }
            }
        }
        return -1;
    }
    private static int[] fibonacci(int length) {
        int[] fibonacci = new int[length];
        fibonacci[0] = 1;
        fibonacci[1] = 1;
        for (int i = 2; i < length; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        return fibonacci;
    }
    //二叉树查找
    public static boolean BinaryTreeSearch(Comparable [] data, Comparable target){
        LinkedBinarySearchTree tree = new LinkedBinarySearchTree();
        for (int a = 0; a< data.length; a++){
            tree.addElement(data[a]);
        }
        if (tree.find(target) == target)
            return true;
        else
            return false;
    }
    //分块查找
    public static boolean BlockSearch(Comparable[] data ,Comparable target,int lump){
        if(target == blockSearch(data,target,lump))
            return true;
        else
            return false;
    }
    private static Comparable blockSearch(Comparable[] data ,Comparable target,int lump){
        int temp = data.length / lump;
        Comparable result = null;
        Comparable[] tp= new Comparable [temp];
        for (int a = 0;a< data.length; a = a+ temp){
            if (data[a].compareTo(target) > 0){
                int c = 0;
                for (int j =a - temp; j < a; j++){
                    tp[c] = data[j];
                    c++;
                }
                result = linearSearch(tp,target);
                break;
            }
            else if (data[a].compareTo(target) == 0){
                result = data[a];
                break;
            }
        }
        return result;
    }
    //哈希查找
    public static int searchHash(int[] hash, int hashLength, int key) {
        int hashAddress = key % hashLength;

        while (hash[hashAddress] != 0 && hash[hashAddress] != key) {
            hashAddress = (++hashAddress) % hashLength;
        }
        if (hash[hashAddress] == 0)
            return -1;
        return hashAddress;
    }
    public static void insertHash(int[] hash, int hashLength, int data) {
        int hashAddress = data % hashLength;
        while (hash[hashAddress] != 0) {
            hashAddress = (++hashAddress) % hashLength;
        }
        hash[hashAddress] = data;
    }
}

